package com.leetcode.partition16;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/2/3 14:29
 */
public class LC1568使陆地分离的最少天数 {

    private static final int N = 1000, M = 4 * N;
    private static final int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static int[] h = new int[N], e = new int[M], ne = new int[M];
    private static boolean[][] st = new boolean[35][35];
    private static int[][] graph;

    private static int idx = 1, timestamp = 0, cutCnt = 0, root = -1;
    private static int[] dfn = new int[N], low = new int[N];
    private static boolean[] cut = new boolean[N];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        int n = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            ss = reader.readLine().split(" ");
            for (int j = 0; j < m; j++) grid[i][j] = Integer.parseInt(ss[j]);
        }
        writer.write(minDays(grid) + "\n");
        writer.flush();
    }

    public static int minDays(int[][] grid) {
        graph = grid;
        //如果连通块数量不是1，直接返回0
        int r = grid.length, c = grid[0].length, cnt = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 0 || st[i][j]) continue;
                dfs(i, j);
                cnt++;
            }
        }
        if (cnt > 1) return 0;
        int landCnt = 0;
        //给相邻的陆地建图
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 0) continue;
                landCnt++;
                for (int[] dir : dirs) {
                    int nx = dir[0] + i, ny = dir[1] + j;
                    if (nx < 0 || nx >= r || ny < 0 || ny >= c || grid[nx][ny] == 0) continue;
                    int idx1 = i * c + j, idx2 = nx * c + ny;
                    add(idx1, idx2);
                }
            }
        }
        if (landCnt == 0) return 0;
        if (landCnt == 1) return 1;
        //tarjan找割点，如果有割点，只需要一次就可以使陆地分离；如果不存在割点，只需要两次就可以使陆地分离（矩形四个角的位置）
        for (int i = 0; i < r * c; i++) {
            if (dfn[i] == 0) {
                root = i;
                tarjan(i);
            }
        }
        if (cutCnt > 0) return 1;
        return 2;
    }

    private static void tarjan(int u) {
        dfn[u] = low[u] = ++timestamp;
        int flag = 0;
        for (int i = h[u]; i != 0; i = ne[i]) {
            int v = e[i];
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
                if (dfn[u] <= low[v]) {
                    flag++;
                    if (u != root || flag > 1) {
                        cut[u] = true;
                        cutCnt++;
                    }
                }
            } else low[u] = Math.min(low[u], dfn[v]);
        }
    }

    private static void dfs(int x, int y) {
        st[x][y] = true;
        for (int[] dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx < 0 || nx >= graph.length || ny < 0 || ny >= graph[0].length || graph[nx][ny] == 0 || st[nx][ny]) continue;
            dfs(nx, ny);
        }
    }

    private static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}
